package generator;

import com.jme3.math.FastMath;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Set;
import misc.Vector3i;

public abstract class DungeonGenerator {
    protected static Random rand;
    protected static Dungeon dungeon = new Dungeon();
    protected static int numRooms = 10;
    protected static Vector3i placementRadius = new Vector3i(10,0,10);
    protected static boolean allowOverlappingRooms = true;
    protected static boolean growRadius = true;

    public static Dungeon generateDungeon(long seed) {
        rand = new Random(seed);
        for(int i=0; i<numRooms; i++) {
            addRoomToDungeon(makeRoom());
        }
	surroundConstructsWithWalls(new ArrayList<DungeonConstruct>(dungeon.getRooms()));
        System.out.println("Generated "+numRooms+" rooms. Final count: "+dungeon.getRooms().size()+" rooms.");
        connectRooms();
	surroundConstructsWithWalls(new ArrayList<DungeonConstruct>(dungeon.getTunnels()));
        return dungeon;
    }

    protected static DungeonRoom makeRoom() {
        //TODO make multiple room templates
        DungeonRoom room = new DungeonRoom();
        int xCells = rand.nextInt(DungeonRoom.maxSize.getX()-DungeonRoom.minSize.getX()+1)+DungeonRoom.minSize.getX();
        int zCells = rand.nextInt(DungeonRoom.maxSize.getZ()-DungeonRoom.minSize.getZ()+1)+DungeonRoom.minSize.getZ();
        for(int x=0; x<xCells; x++) {
            for(int z=0; z<zCells; z++) {
		room.addFloorCell(new DungeonCellFloor(new Vector3i(x,0,z), room));
            }
        }
        return room;
    }

    protected static void addRoomToDungeon(DungeonRoom room) {
        boolean roomPlaced = false;
        while(!roomPlaced) {
            Vector3i offset = generateRandomOffset();
            room.applyOffset(offset);
            Collection<DungeonConstruct> overlappingConstructs = dungeon.getOverlappingConstructs(room);
            if(allowOverlappingRooms) {
                for(DungeonConstruct overlappingConstruct : overlappingConstructs) {
                    mergeConstructs(room, overlappingConstruct);
                }
            }
            if(allowOverlappingRooms || overlappingConstructs.isEmpty()) {
                dungeon.addConstruct(room);
                roomPlaced = true;
            }
            //Be careful using growRadius == false && allowOverlappingRooms == false. You may get stuck in an infinite loop.
            if(growRadius) {
                incrementPlacementRadius();
            }
        }
    }
    
    protected static void mergeConstructs(DungeonConstruct construct, DungeonConstruct overlappingConstruct) {
	System.out.println("Merging constructs!");
	dungeon.removeConstruct(overlappingConstruct);
	construct.addCells(overlappingConstruct.getCells());
    }

    protected static void surroundConstructsWithWalls(Collection<DungeonConstruct> constructs) {
	for(DungeonConstruct construct : constructs) {
	    for(DungeonCellFloor floorCell : construct.getFloorCells()) {
		for(Vector3i location : getSurroundingLocations(floorCell.getLocation())) {
		    if(!dungeon.locationOccupied(location)) {
			DungeonCellWall cell = new DungeonCellWall(location, construct);
			construct.addWallCell(cell);
			dungeon.addCell(cell);
		    }
		}
	    }
	}
    }

    protected static Collection<Vector3i> getSurroundingLocations(Vector3i location) {
	List<Vector3i> surroundingLocations = new ArrayList<Vector3i>();
        surroundingLocations.add(location.clone().addX(1));
        surroundingLocations.add(location.clone().addX(-1));
        surroundingLocations.add(location.clone().addZ(1));
        surroundingLocations.add(location.clone().addZ(-1));
	surroundingLocations.add(location.clone().addX(1).addZ(1));
	surroundingLocations.add(location.clone().addX(1).addZ(-1));
	surroundingLocations.add(location.clone().addX(-1).addZ(1));
	surroundingLocations.add(location.clone().addX(-1).addZ(-1));
        return surroundingLocations;
    }

    protected static Vector3i generateRandomOffset() {
        int xOffset = rand.nextInt(placementRadius.getX()+1);
        int zOffset = rand.nextInt(placementRadius.getZ()+1);
        if(rand.nextBoolean())
            xOffset = -xOffset;
        if(rand.nextBoolean())
            zOffset = -zOffset;
        return new Vector3i(xOffset, 0, zOffset);
    }

    protected static void incrementPlacementRadius() {
        placementRadius.add(Dungeon.roomSpread, 0, Dungeon.roomSpread);
    }

    protected static void connectRooms() {
        for(int i=0; i<dungeon.getRooms().size()-1; i++) {
            DungeonRoom startRoom = dungeon.getRooms().get(i);
            DungeonRoom endRoom = dungeon.getRooms().get(i+1);
            List<Vector3i> tunnelLocations = findPath(startRoom, endRoom);
            DungeonTunnel tunnel = new DungeonTunnel();
            for(Vector3i location : tunnelLocations) {
		if(!dungeon.locationOccupied(location)) {
		    tunnel.addFloorCell(new DungeonCellFloor(location, tunnel));
		} else {
		    DungeonCell cell = dungeon.getCellAtLocation(location);
		    if(cell instanceof DungeonCellWall) {
			cell.getOwner().removeWallCell((DungeonCellWall)cell);
			dungeon.removeCell(cell);
			tunnel.addFloorCell(new DungeonCellFloor(location, tunnel));
		    }
		}
            }
            dungeon.addConstruct(tunnel);
            System.out.println("Tunnel placed.");
        }
    }

    protected static List<Vector3i> findPath(DungeonRoom startRoom, DungeonRoom endRoom) {
	// Choose random start and end cells from each room
	DungeonCell startCell = startRoom.getFloorCells().get(rand.nextInt(startRoom.getFloorCells().size()));
	DungeonCell endCell = endRoom.getFloorCells().get(rand.nextInt(endRoom.getFloorCells().size()));

        Map<Vector3i, Integer> costs = new HashMap<Vector3i, Integer>();  // Cost from start along best known path.
        costs.put(startCell.getLocation(), 0);

        Set<Vector3i> closedset = new HashSet<Vector3i>();  // The set of nodes already evaluated.
        PriorityQueue<TunnelPlacement> openset = new PriorityQueue<TunnelPlacement>(100, new TunnelPlacementComparator(endCell.getLocation()));  // The set of tentative nodes to be evaluated,
        openset.add(new TunnelPlacement(startCell.getLocation(), costs.get(startCell.getLocation())));  // initially containing the start node

        Map<Vector3i, Vector3i> predecessorMap = new HashMap<Vector3i, Vector3i>();  // The map of navigated nodes.

        TunnelPlacement current;
        while (!openset.isEmpty()) {
            current = openset.poll();


            if (current.getLocation().equals(endCell.getLocation())) {
                return reconstructPath(predecessorMap, endCell.getLocation());
            }

            openset.remove(current);
            closedset.add(current.getLocation());
            for (Vector3i neighborLocation : neighborLocations(current.getLocation())) {
                if (!closedset.contains(neighborLocation)) {
                    TunnelPlacement neighbor = new TunnelPlacement(neighborLocation, current.getCost() + actualCostBetween(current.getLocation(), neighborLocation, predecessorMap.get(current.getLocation()), startRoom, endRoom));

                    if (!openset.contains(neighbor) || neighbor.getCost() < costs.get(neighborLocation)) {
                        openset.add(neighbor);
                        predecessorMap.put(neighbor.getLocation(), current.getLocation());
                        costs.put(neighbor.getLocation(), neighbor.getCost());
                    }
                }
            }
        }

        return null;
    }

    public static int actualCostBetween(Vector3i current, Vector3i next, Vector3i previous, DungeonRoom startRoom, DungeonRoom endRoom) {
        if(dungeon.locationOccupied(next)) {
	    //moving through an existing construct
            DungeonConstruct construct = dungeon.getCellAtLocation(next).getOwner();
	    if(construct instanceof DungeonTunnel) {
		return 1; //best movement through an existing tunnel
	    } else if(construct instanceof DungeonRoom && !construct.equals(startRoom) && !construct.equals(endRoom)) {
		return 10; //penalty for moving through another room
	    } else {
		return 2; //movement through the start/end rooms (giving them a bonus causes tunnels to gravitate toward room corners?)
	    }
        } else {
	    //moving through empty space
	    if(previous != null && (next.getX() == previous.getX() || next.getZ() == previous.getZ())) {
		return 3; //a straight line
	    } else {
		return 5; //a bend
	    }
	}
    }

    public static int bestCostBetween(Vector3i current, Vector3i goal) {
	return Math.round(FastMath.abs(goal.getX() - current.getX()) +
			  FastMath.abs(goal.getY() - current.getY()) +
			  FastMath.abs(goal.getZ() - current.getZ()));
    }

    protected static Collection<Vector3i> neighborLocations(Vector3i boardLocation) {
        List<Vector3i> neighbors = new ArrayList<Vector3i>();
        neighbors.add(boardLocation.clone().addX(1));
        neighbors.add(boardLocation.clone().addX(-1));
        neighbors.add(boardLocation.clone().addZ(1));
        neighbors.add(boardLocation.clone().addZ(-1));
        return neighbors;
    }

    protected static List<Vector3i> reconstructPath(Map<Vector3i, Vector3i> predecessorMap, Vector3i currentNode) {
        if (predecessorMap.containsKey(currentNode)) {
            List<Vector3i> path = reconstructPath(predecessorMap, predecessorMap.get(currentNode));
            path.add(currentNode);
            return path;
        } else {
            return new ArrayList<Vector3i>();
        }
    }
}
